package set.src;

import java.util.concurrent.atomic.AtomicMarkableReference;

import set.CMDR.SnapshotCounter;


/**
 * 
 * @author Erik Sapir & Lior Zibi
 * 
 * Lock-free List based on M. Michael's algorithm.
 * 
 * @param T Item type.
 */
public class LockFreeList<T> implements Set<T>{
	/**
	 * First list node
	 */
	volatile Node m_head;
	  
	/**
	 * counter for number of element in the list
	 */
	volatile private SnapshotCounter m_counter;
  
	/**
	 *Constructor
	 */
	public LockFreeList(int numOfThreads) {
		System.out.println("\n\tSet Is: LockFree List\n");
		
		// Add sentinels to start and end
		this.m_head  = new Node(Integer.MIN_VALUE);
		Node tail = new Node(Integer.MAX_VALUE);

		while (!m_head.m_next.compareAndSet(null, tail, false, false));
    
		m_counter = new SnapshotCounter(numOfThreads);   
	}

	public boolean add(T item, int threadID) {
		SnapshotCounter pToCounter = m_counter;
		int key = item.hashCode();
		
		while (true) {
			// find predecessor and current entries
			Window window = find(m_head, key, threadID);
			Node pred = window.m_pred, curr = window.m_curr;
			
			// is the key present?
			if (curr.m_key == key) {
				//element already in list - nothing to add
				return false;
			} else {
				// add new node to list
				Node node = new Node(item);
				node.m_next = new AtomicMarkableReference<Node>(curr, false);
				
				if (pred.m_next.compareAndSet(curr, node, false, false)) {
					
					//element added successfully - increment number of element in list
					pToCounter.inc(threadID);

					return true;
				}
			}
		}
	}
  
	
	public boolean remove(T item, int threadID) {
		int key = item.hashCode();
		boolean snip;
    
		while (true) {
			// find predecessor and current entries
			Window window = find(m_head, key, threadID);
			Node curr = window.m_curr;

			// is the key present?
			if (curr.m_key != key) {
				//element is not in list - nothing to remove
				return false;
			} else {
				// snip out matching node
				Node succ = curr.m_next.getReference();
				snip = curr.m_next.attemptMark(succ, true);
				if (!snip)
					continue;
        
				//lets give it one shot
				snip = window.m_pred.m_next.compareAndSet(curr, succ, false, false);
				
				if (snip){
					//removed successfully - decrement number of element in list
					m_counter.dec(threadID);
				}
				
				return true;
			}
		}
	}
  
	public boolean contains(T item, int threadID) {
		
		int key = item.hashCode();
		// find predecessor and current entries
		Window window = find(m_head, key, threadID);
		Node curr = window.m_curr;
		
		//return true iff element found in list
		return (curr.m_key == key);
	}
  
	  
	public void clean(int threadID) {

		Node curr = m_head.m_next.getReference();
		Node succ;
		int key = curr.m_key;
		
		boolean snip;
	
		//remove each and every element from  the list
		while(true){ 
			if (key == Integer.MAX_VALUE)
				return;
			
			succ = curr.m_next.getReference();
			
			//try to delete
			snip = m_head.m_next.compareAndSet(curr, succ, false, false);
			
			if(snip){
				curr =  m_head.m_next.getReference();
				key = curr.m_key;
		
				//removed successfully - decrement number of element in list
				m_counter.dec(threadID);
			}
		}
	}

	public boolean isEmpty(int threadID) {
		boolean[] marked = {false}; // is curr marked?
	 
		Node curr = this.m_head.m_next.getReference();
    
		//search for an element in the list that wasn't logically deleted
		while (curr.m_key != Integer.MAX_VALUE)	{
			curr=curr.m_next.get(marked);
    	
			//make sure not logically deleted
			if (!marked[0])
				return false;
		}
    
		return true;
	}

	public int size(int threadID) {
	
		return m_counter.scan_sum();
	}
	
	/**
	 * If element is present, returns node and predecessor. If absent, returns
	 * node with least larger key.
	 * @param head start of list
	 * @param key key to search for
	 * @return If element is present, returns node and predecessor. If absent, returns
	 * node with least larger key.
	 */
	public Window find(Node head, int key, int threadID) {
		Node pred = null, curr = null, succ = null;
		boolean[] marked = {false}; // is curr marked?
		boolean snip;
		retry: while (true) {
			pred = head;
			curr = pred.m_next.getReference();
		
			while (true) {
				succ = curr.m_next.get(marked); 
        
				while (marked[0]) {           // replace curr if marked
					snip = pred.m_next.compareAndSet(curr, succ, false, false);
					if (!snip) 
						continue retry;
					
					//removed successfully - decrement number of element in list
					m_counter.dec(threadID);
					
					curr = pred.m_next.getReference();
					succ = curr.m_next.get(marked);
				}
				if (curr.m_key >= key)
					return new Window(pred, curr);
				pred = curr;
				curr = succ;
			}
		}
	}
	
	/**
	 * list node
	 */
	private class Node {

		/**
		 * actual item
		 */
		final T m_item;
	
		/**
		 *item's hash code
		 */
		final int m_key;
    
		/**
		 * next node in list
		 */
		AtomicMarkableReference<Node> m_next;

		/**
		 * Constructor for usual node
		 * @param item element in list
		 */
		Node(T item) {      // usual constructor
			this.m_item = item;
			this.m_key = item.hashCode();
			this.m_next = new AtomicMarkableReference<Node>(null, false);
		}
    
		/**
		 * Constructor for sentinel node
		 * @param key should be min or max int value
		 */
		Node(int key) { // sentinel constructor
			this.m_item = null;
			this.m_key = key;
			this.m_next = new AtomicMarkableReference<Node>(null, false);
		}
	}
  
	/**
	 * Pair of adjacent list entries.
	 */
	class Window {
		/**
		 * Earlier node.
		 */
		final public Node m_pred;
		
		/**
		 * Later node.
		 */
		final public Node m_curr;

		/**
		 * Constructor.
		 */
		Window(Node pred, Node curr) {
			this.m_pred = pred; this.m_curr = curr;
		}
	}
}
